'''
https://leetcode.cn/problems/profitable-schemes/description/
'''
from collections import defaultdict
from functools import cache
from typing import List


class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        n_task = len(profit)
        MOD = 10 ** 9 + 7

        # i是考察第i个任务的介绍
        # j时当前有多少人已经工作
        # rest_profit: 离minProfit还差多远, <0 表示已经满足
        @cache
        def f(i, j, rest_profit):
            if i == n_task:
                return 1 if rest_profit <= 0 else 0
            res = f(i + 1, j, rest_profit)
            if j + group[i] <= n:
                ### ！！！max(0, xxx)  达标就行，不用减成负值，不然可能性太多了
                res = (res + f(i + 1, j + group[i], max(0, rest_profit - profit[i]))) % MOD
            return res
        return f(0, 0, minProfit)

    # 改dp 打表
    def profitableSchemes2(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        n_task = len(profit)
        MOD = 10 ** 9 + 7
        dp = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(n_task + 1)]
        # 初始化 i == n_task, rest_profit = 0: dp[n_task][j][0] = 1
        for j in range(n + 1):
            dp[n_task][j][0] = 1
        # 第一维度依赖后边的，第二维度依赖后边的，第三维度依赖前边的
        for i in range(n_task-1, -1, -1):
            for j in range(n, -1, -1):
                for rest_profit in range(minProfit + 1):
                    res = dp[i+1][j][rest_profit]
                    if j + group[i] <= n:
                        # max, 负数和0都达标,一样的
                        res = (res + dp[i + 1][j + group[i]][max(0, rest_profit - profit[i])]) % MOD
                    dp[i][j][rest_profit] = res
        return dp[0][0][minProfit]

    # 改dp 打表 + 状态压缩
    def profitableSchemes3(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        n_task = len(profit)
        MOD = 10 ** 9 + 7
        A = [[0] * (minProfit + 1) for _ in range(n + 1)]
        # 初始化 i == n_task, rest_profit = 0: A[n_task][j][0] = 1
        for j in range(n + 1):
            A[j][0] = 1
        # 第一维度依赖后边的，第二维度依赖后边的，第三维度依赖前边的
        for i in range(n_task-1, -1, -1):
            B = [[0] * (minProfit + 1) for _ in range(n + 1)]
            for j in range(n, -1, -1):
                for rest_profit in range(minProfit + 1):
                    res = A[j][rest_profit]
                    if j + group[i] <= n:
                        # max, 负数和0都达标,一样的
                        res = (res + A[j + group[i]][max(0, rest_profit - profit[i])]) % MOD
                    B[j][rest_profit] = res
            A = B
        return A[0][minProfit]
